package com.hspedu.newData.dmsxl.数组.二分查找;

import com.hspedu.newData.dmsxl.树.LC653两数之和输入二叉搜索树;
import org.junit.Test;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-25 
 * @Version: 1.0
 */

//todo
public class LC74搜索二维矩阵 {

    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix,int target){
        int low = -1,high = matrix.length - 1;
        while (low<high){
            int mid = (high - low+1)/2+low;
            if (matrix[mid][0] <= target){
                low = mid;
            }else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean binarySearchRow(int[] row,int target){
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }

    @Test
    public void test() {
        // 测试代码

        searchMatrix(new int[][]{{1,3,5,7},{10,13,16,20},{23,30,34,60}},13);
    }
}
